<?php
/**
 * 插入排序
 */
function insertion_sort($list)
{
    for($p=1; $p<count($list); $p++){
        $tmp=$list[$p];
        for($j=$p; $j>0 && $tmp<$list[$j-1]; $j--){
            $list[$j]=$list[$j-1];
        }
        $list[$j]=$tmp;
    }
    return $list;
}
/**
 * 希尔排序
 */
function shell_sort($list)
{
    for($gap=count($list)/2; $gap>0; $gap/=2){
        $gap=floor($gap);
        for($i=$gap; $i<count($list); $i++){
            $tmp=$list[$i];
            for($j=$i; $j>=$gap && $tmp<$list[$j-$gap]; $j-=$gap){
                $list[$j]=$list[$j-$gap];
            }
            $list[$j]=$tmp;
        }
    }
    return $list;
}
/**
 * 堆排序
 */
function heap_sort($list)
{
    if(!class_exists("Heap")){
        echo "需要导入 Heap.php 文件\r\n";
        exit;
    }
    $heap=new Heap();
    $heap->insertList($list);
    return $heap->popMinList();
}
/**
 * 堆排序
 * 使用FixedHeap
 */
function heap_sort_2($list)
{
    $size=count($list);
    $heap=new FixedHeap($size);
    $heap->insertList($list);
    return $heap->popMinList();
}
/**
 * 堆排序
 * 使用PHP SPL扩展中的最小堆
 */
function heap_sort_3($list)
{
    $heap=new SplMinHeap();
    foreach($list as $item){
        $heap->insert($item);
    }
    $sort_list=[];
    foreach($heap as $item){
        $sort_list[]=$item;
    }
    return $sort_list;
}
/**
 * 归并排序
 */
function merge_sort($list)
{
    if(!class_exists("MergeSort")){
        echo "需要导入 MergeSort.php 文件\r\n";
        exit;
    }
    return MergeSort::sort($list);
}
/**
 * 快速排序
 */
function quick_sort($list)
{
    $count=count($list);
    if($count<=1){
        return $list;
    }
    $middle=$list[floor($count/2)];
    $smaller=[];
    $larget=[];
    $same=[];
    foreach($list as $item){
        if($item>$middle){
            $larget[]=$item;
        }
        elseif($item<$middle){
            $smaller[]=$item;
        }
        else{
            $same[]=$item;
        }
    }
    $larget=quick_sort($larget);
    $smaller=quick_sort($smaller);
    return array_merge($smaller,$same,$larget);
}
/**
 * 快速排序
 * 使用三数中值分割法
 * 当数组足够小时使用插入排序
 */
function quick_sort_2($list,$little_size=3)
{
    $count=count($list);
    if($count<=$little_size){
        return insertion_sort($list);
    }
    $middle=median_of_tree($list);
    $smaller=[];
    $larget=[];
    $same=[];
    foreach($list as $item){
        if($item>$middle){
            $larget[]=$item;
        }
        elseif($item<$middle){
            $smaller[]=$item;
        }
        else{
            $same[]=$item;
        }
    }
    $larget=quick_sort($larget);
    $smaller=quick_sort($smaller);
    return array_merge($smaller,$same,$larget);
}
function median_of_tree($list)
{
    $count=count($list);
    $middle=floor($count/2);
    $last=$count-1;
    return ($list[0]+$list[$middle]+$list[$last])/3;
}

/**
 * 非比较排序
 * 统计数组信息
 */
function array_analyse($list)
{
    $count=count($list);
    $min=0;$max=0;
    foreach($list as $item){
        if($item<$min){
            $min=$item;
        }
        if($item>$max){
            $max=$item;
        }
    }
    return [$count,$min,$max];
}

/**
 * 桶排序
 */
function bucket_sort($list)
{
    list($count,$min,$max)=array_analyse($list);
    $count_list=array_fill(0,$max-$min+1,0);
    foreach($list as $item){
        $count_list[$item-$min]++;
    }
    $sort_list=[];
    foreach($count_list as $value => $count){
        for($i=0;$i<$count;$i++){
            $sort_list[]=$value;
        }
    }
    return $sort_list;
}
/**
 * 基数排序
 */
function radix_sort($list)
{
    list($count,$min,$max)=array_analyse($list);
    $radix=($max-$min)/$count;
    $bucket_list=[];
    foreach($list as $item){
        $bucket_index=floor(($item-$min)/$radix);
        if(isset($bucket_list[$bucket_index])){
            $bucket_list[$bucket_index][]=$item;
        }
        else{
            $bucket_list[$bucket_index]=[$item];
        }
    }
    $sort_list=[];
    for($i=0;$i<=$count;$i++){
        if(isset($bucket_list[$i])){
            $bucket=$bucket_list[$i];
            $sort_list=array_merge($sort_list,insertion_sort($bucket));
        }
    }
    return $sort_list;
}
/**
 * 对于字符串的基数排序
 */
function string_radix_sort($list)
{

}
/**
 * 计数基数排序
 */
function counting_radix_sort($list)
{

}
/**
 * 计数基数排序
 * 使用一个数组实现
 */
function counting_radix_sort_2($list)
{

}
